package sort;

public class sorts {
	
	public static void print(int [] array) {
		for(int i = 0; i < array.length;i++) {
			System.out.print(array[i]+ " ");
		}
		System.out.print("\n");
	}
	
//插入排序
//	1.从第一个元素开始，该元素可以认为已经被排序 
//	2.取出下一个元素a，在已经排序的元素序列中从后向前扫描 
//	3.如果已排序中的元素b大于a，则将元素b后移一个位置 
//	4.重复步骤3，直到找到已排序的元素x小于或者等于元素a 
//	5.将元素a插入到x的后面 
//	6.重复步骤2~5 
	public static void insertionSort(int [] array) {
		for(int i = 0; i < array.length; i++) {
			//待插入的数据  
            int toBeInsertedValue = array[i];  
            int j;  
            for(j=i;j>0;j--){  
                if(array[j-1]>toBeInsertedValue){  
                    //将比toBeInsertedValue大的元素全部后移  
                    array[j]=array[j-1];  
                    continue;  
                }  
                break;  
            }  
            //插入新元素  
            array[j]=toBeInsertedValue;  
		}
		print(array);
	}
	
//	选择排序
//	1. 未排序序列中找到最小元素，存放到排序序列的起始位置 
//	2. 再从剩余未排序元素中继续寻找最小元素，然后放到排序序列末尾 
//	3. 以此类推,直到所有元素均排序完毕 
//
//	比较复杂度：n(n-1)/2 
//	交换(赋值)复杂度：n-1 
//	优点：相比冒泡排序来讲，交换的次数减少了 
//	缺点：相对快速排序，比较次数仍然是n² 
	public static void selectionSort(int[] array){  
        for(int i=0;i<array.length-1;i++){  
            //最小数存放位置  
            int minPosition = i;  
            for(int j=i+1;j<array.length;j++){  
                if(array[j]<array[minPosition]){  
                    //新的最小数位置  
                    minPosition = j;  
                }  
            }  
            //找到剩余元素中的最小数，并将其交换至起始位置  
            swap(array, i, minPosition);  
        }  
        print(array);
    }  
	public static void swap(int[] array,int a,int b){  
        int temp = array[a];  
        array[a] = array[b];  
        array[b] = temp;  
    } 
	
//	冒泡排序
//	1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。 
//	2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。 
//	3. 针对所有的元素重复以上的步骤，除了最后一个。 
//	4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
	public static void bubbleSort(int[] array){  
        for(int i=array.length-1;i>=0;i--){  
            for(int j=0;j<i;j++){  
                if(array[j]>array[j+1]){  
                    swap(array, j, j+1);  
                }  
            }  
        }
        print(array);
    }  
	
//	快速排序
//	1. 从数列中挑出一个元素，称为 "基准"（pivot） 
//
//	2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面 （相同的数可以到任一边）。在这个分割结束之后，该基准就处于数列的中间位置。这个称为分割（partition）操作 
//
//	3. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序 
//
//	* 比较复杂度：O(n㏒n) 
//	* 交换(赋值)复杂度：O(n㏒n) 
//	* 优点：比一般的排序都要快 
	public static void quickSort(int[] array) {     
	    if (array == null || array.length== 0) {     
	         return;     
	    }     
	    quickSort(array,0,array.length-1); 
	    print(array);
	} 
	
	private static void quickSort(int[] array, final int start, final int end){  
        //数组长度<=1退出  
        if(start>=end){  
            return;  
        }  
        //数组长度==2,比较两个元素的大小  
        if(end-start==1){  
            if(array[start]>array[end]){  
                swap(array,start,end);  
            }  
            return;  
        }  
          
        //用来进行比较的数  
        int compareNumber = array[start];  
        int middlePosition = 0;  
        int i = start;  
        int j = end;  
        for(;;i++,j--){  
              
            //从数组首端开始迭代(不包括compareNumber)，如果数组的数<compareNumber，不做移动  
            while(array[i]<compareNumber&&i<j){  
                i++;  
            }         
            //从数组尾端迭代，如果数组的数>=compareNumber，不做移动  
              
            while(array[j]>compareNumber&&i<j){  
                j--;  
            }             
              
            if(i>=j){  
                if(array[j]>compareNumber){  
                    middlePosition = j;  
                }else{  
                    middlePosition = (j+1);  
                }  
                break;  
            }  
            //从数组首端开始迭代，得到大于compareNumber的数array[i]，此时从尾端迭代直至得到<=compareNumber的数  
            //array[j],交换这两个数的位置，然后继续迭代  
            swap(array,i,j);  
        }  
        //递归排序  
        quickSort(array,start,middlePosition-1);  
        quickSort(array,middlePosition,end);  
    } 
	
	
//	合并排序
//	合并算法，指的是将两个已经排序的序列合并成一个序列的操作 
//
//	操作步骤： 
//	1. 建立一个数组C用来存放合并后的数 
//	2. 从数组A和数组B的首端开始比较，将大的元素放入C中 
//	3. 重复2操作，直至其中一个数组的元素被用完，则将另一个数组中剩余的元素拷贝到C中 
//
//	比较复杂度：n㏒n 
//	交换(赋值)复杂度：n㏒n 
//	优点：比较快速的排序算法 
//	缺点：需要额外的空间存放临时数组 
	private static void merge(int[] array,final int left,final int leftEnd, final int rightEnd){  
        Integer[] mergeResult = new Integer[rightEnd-left+1];  
        int i = 0; //mergeResult的下标  
        int j = left; //left 的下标  
        int k = leftEnd+1; //right 的下标  
          
        //将两个数组中较小的元素拷贝到mergeResult中  
          
        while(j<=leftEnd&&k<=rightEnd){  
            if(array[j]<array[k]){  
                mergeResult[i++] = array[j++];  
            }else{  
                mergeResult[i++] = array[k++];  
            }  
        }  
        //将另一个数组中剩余的元素拷贝到mergeResult中  
        while(j<=leftEnd){  
            mergeResult[i++] = array[j++];  
        }  
        while(k<=rightEnd){  
            mergeResult[i++] = array[k++];  
        }     
        //copy mergeResult to array  
        int leftPos = left;  
        for(int m=0;m<mergeResult.length;m++,leftPos++){  
            array[leftPos] = mergeResult[m];  
        }  
    }  
	private static void mergeSort(int[] array,final int left,final int leftEnd, final int rightEnd){      
        if(left>=rightEnd){            
            return;  
        }  
        mergeSort(array,left,(left+leftEnd)/2,leftEnd);  
        mergeSort(array,leftEnd+1,(leftEnd+1+rightEnd)/2,rightEnd);  
        merge(array,left,leftEnd,rightEnd);  
    } 
	
	public static void mergeSort(int[] array){  
        mergeSort(array,0,(array.length)/2,array.length-1);  
        print(array);
    }
	
//main函数
	public static void main(String[] args) {
		System.out.println("\n插入排序");
		int a[] = {1,9,5,3,2};
		insertionSort(a);
		System.out.println("\n选择排序");
		int b[] = {1,9,5,3,2};
		selectionSort(b);
		System.out.println("\n冒泡排序");
		int c[] = {1,9,5,3,2};
		bubbleSort(c);
		
		System.out.println("\n快速排序");
		int d[] = {1,9,5,3,2};
		quickSort(d);
		
		System.out.println("\n合并排序");
		int [] e = {1,9,5,3,2};
		mergeSort(e);
		
		
	}
}
